// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const int N = 2e6+50, M = 26;

struct node {
    int nxt[M], dep, siz, fa;
} nodes[N];

#define tm _tm

char tm[N];
char *a[N];
int tot;
int newnode(int fa = 0) {
    memset(&nodes[++tot], 0, sizeof(node));
    if (fa) {
        nodes[tot].fa = fa;
        nodes[tot].dep = nodes[fa].dep + 1;
    }
    return tot;
}

int root;

void insert(char a[], int n) {
    int cur = root;
    for (int i=0; i<n; ++i) {
        int now = a[i] - 'A';
        if (!nodes[cur].nxt[now]) {
            nodes[cur].nxt[now] = newnode(cur);
        }
        cur = nodes[cur].nxt[now];
    }

    ++nodes[cur].siz;
}

vector<int> dat[N];

int n, k;

int main(int argc, char const *argv[]) {
    // code
    int t;
    scanf("%d", &t);
    for (int kk=0; kk<t; ++kk) {
        // cin >> n >> k;
        scanf("%d%d", &n, &k);
        int maxlen = 0;

        tot = 0;
        root = newnode();
        for (int i=0; i<n; ++i) {
            scanf("%s", tm);
            int len  = strlen(tm);
            // a[i] = new char[len + 5];
            // a[i] = (char*)malloc(len + 5);
            maxlen = max(maxlen, len);
            // strcpy(a[i], tm);
            // dbg(i, len);
            insert(tm, len);
        }
        for (int i=0; i<=maxlen + 5; ++i)
            dat[i].clear();

        // dbg(maxlen, tot);
        // for (int i=1; i<=tot; ++i) {
        //     dbg(i, nodes[i].fa, nodes[i].siz);
        // }

        for (int i=2; i<=tot; ++i) {
            dat[nodes[i].dep].push_back(i);
        }
        int ans = 0;
        for (int i=maxlen; i>=1; --i) {
            for (int id : dat[i]) {
                // dbg(id, nodes[id].siz, nodes[id].fa);
                if (nodes[id].siz >= k) {
                    int num = nodes[id].siz / k;
                    // dbg(num, i, nodes[id].siz, id);
                    ans += num * i;
                    nodes[id].siz -= num * k;
                }

                nodes[nodes[id].fa].siz += nodes[id].siz;
            }
        }
        // for (int i=0;i<n; ++i)
        //     free(a[i]);
        printf("Case #%d: %d\n", kk+1, ans);
    }
    return 0;
}
